# 翻转链表


class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 构建一个列表
def build_linked_list(arr: list) -> ListNode:
    if not arr:
        return
    
    head = ListNode(arr[0])
    curr = head
    for val in arr[1: ]:
        curr.next = ListNode(val)
        curr = curr.next  
    return head

def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=" -> " if current.next else " -> None")
        current = current.next
    print()  # 换行



class Solution:
    def reverseList(self, head):

        pre = None
        cur = head
        while cur:
            nxt = cur.next # 保存下一个节点
            cur.next = pre # 当前节点指向前驱节点
            pre = cur # 保存前驱节点
            cur = nxt # 移动到下一位置
    
        return pre

        
if __name__ == "__main__":

    arr = [1,2,3,4,5]
    print(arr)
    head = build_linked_list(arr)
    sol = Solution()

    result = sol.reverseList(head)
    print_linked_list(result)




